package features.advance.leetcode.tree.hard;

import features.advance.leetcode.tree.model.TreeNode;
import features.advance.leetcode.util.TreeUtil;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @author LIN
 * @date 2021-06-22
 */
public class Offer37 {

    public static void main(String[] args) {

        Codec codec = new Codec(){
            @Override
            public String serialize(TreeNode root) {
                if (root == null) {
                    return "X";
                }
                String l = "(" + serialize(root.left) + ")";
                String r = "(" + serialize(root.right) + ")";
                return  l + root.val + r;
            }

            @Override
            public TreeNode deserialize(String data) {
                int[] ptr = {0};
                return parse(data, ptr);
            }

            public TreeNode parse(String data, int[] ptr) {
                if (data.charAt(ptr[0]) == 'X') {
                    ++ptr[0];
                    return null;
                }
                TreeNode cur = new TreeNode(0);
                cur.left = parseSubtree(data, ptr);
                cur.val = parseInt(data, ptr);
                cur.right = parseSubtree(data, ptr);
                return cur;
            }

            public TreeNode parseSubtree(String data, int[] ptr) {
                ++ptr[0]; // 跳过左括号
                TreeNode subtree = parse(data, ptr);
                ++ptr[0]; // 跳过右括号
                return subtree;
            }

            public int parseInt(String data, int[] ptr) {
                int x = 0, sgn = 1;
                if (!Character.isDigit(data.charAt(ptr[0]))) {
                    sgn = -1;
                    ++ptr[0];
                }
                while (Character.isDigit(data.charAt(ptr[0]))) {
                    x = x * 10 + data.charAt(ptr[0]++) - '0';
                }
                return x * sgn;
            }
        };
        String data = "[1,2,3,7,6,4,5,null,null,null,null,null,null,11,12]";
        TreeNode root = TreeUtil.stringToTreeNode(data);
        System.out.println(root);

        String serialize = codec.serialize(root);
        System.out.println(serialize);
        TreeNode deserialize = codec.deserialize(serialize);
        System.out.println(deserialize);


    }

    static class Codec {
        public String rserialize(TreeNode root, String str) {
            if (root == null) {
                str += "None,";
            } else {
                str += root.val + ",";
                str = rserialize(root.left, str);
                str = rserialize(root.right, str);
            }
            return str;
        }
        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
            return rserialize(root, "");
        }

        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            String[] data_array = data.replaceAll("\\[","").replaceAll("\\]","").split(",");
            List<String> data_list = new LinkedList<String>(Arrays.asList(data_array));
            return rdeserialize(data_list);
        }

        public TreeNode rdeserialize(List<String> l) {
            if(l.isEmpty()){
                return null;
            }
            if (l.get(0).equals("null")) {
                l.remove(0);
                return null;
            }

            TreeNode root = new TreeNode(Integer.valueOf(l.get(0)));
            l.remove(0);
            root.left = rdeserialize(l);
            root.right = rdeserialize(l);

            return root;
        }
    }

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));
}
